#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=152 lang=cpp
 *
 * [152] 乘积最大子数组
 */

// @lc code=start
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int sz = nums.size(); int res = 0;
        vector<vector<int>> dp(2, vector<int>(sz, 0));
        // 0表示最大正整数, 1表示绝对值最大负数
        dp[0][0] = nums[0]; dp[1][0] = nums[0];
        res = max(dp[0][0], dp[1][0]);
        for (int i = 1; i < sz; i++) {
            // 本质上就是允许你出负数, 但是不允许你错误地乘出整数
            if (nums[i] < 0) {
                dp[0][i] = dp[1][i - 1] * nums[i];
                dp[1][i] = dp[0][i - 1] <= 0 ? nums[i] : dp[0][i - 1] * nums[i];
            } else {
                dp[0][i] = dp[0][i - 1] <= 0 ? nums[i] : dp[0][i - 1] * nums[i];
                dp[1][i] = dp[1][i - 1] * nums[i];
            }
            res = max(res, max(dp[0][i], dp[1][i]));
        }
        return res;
    }
};
// @lc code=end

